1. Field of Invention
The present invention relates generally to the field of hashing. More specifically, the present invention is related to various hashing techniques for maintaining running aggregates based on the estimated number of distinct groups in a drawer.
2. Discussion of Related Art
Hashing has long been an important area, both in database research, and in other areas of computer science. There is a rich literature on perfect hashing (e.g., see the book by Cormen et al. entitled, “Introduction to Algorithms, Second Edition,” and the paper to Czech et al. entitled, “An optimal algorithm for generating minimal perfect hash functions”), though databases have traditionally used variants of chained hashing. Recently, several researchers have investigated using cuckoo hashing, a dynamic collision-free technique, for query processing (e.g., see the paper to Pagh et al. entitled, “Cuckoo hashing,” the paper to Zukowski et al. entitled, “Architecture-conscious hashing,” and the paper to Ross entitled, “Efficient hash probes on modern processors”). However, none of the previously described hashing techniques apply precomputed perfect hash functions to grouped aggregation queries.
The following patents and patent publications provide a general background describing various hashing techniques, however, as mentioned above, they fail to apply a precomputed perfect hash function to grouped aggregation queries.
The U.S. patent publication to Kenneth Ross (2007/0294506) discloses a hash scheme for processors and particularly describes a variant of cuckoo hashing, which minimizes branch mispredictions.
The U.S. patent publication to Fonroura et al. (2007/0271268) discloses using a mapping table to lookup a token and also discloses using a minimal perfect hash table when the token values are sparse in the domain.
The U.S. patent publication to Hugues Hoppe (2007/0245119) describes how to construct a perfect hash table for sparse variable size data.
The U.S. patent publication to Daniar Hussain (2007/0083531) describes an approach to generate parameters in polynomial hash functions, run them against the whole dataset, and choose the one with lowest collision.
The U.S. Patent to Shetty et al. (U.S. Pat. No. 7,039,764) describes a method wherein a unique key is received and a hash is searched for a match to the unique key. Concurrently with searching the hash, a cache is searched for the match to the unique key and information regarding the unique key is obtained.
The U.S. Patent to Fujiwara et al. (U.S. Pat. No. 6,381,601) describes a hash method which involves multiple bitmaps to remove duplicates efficiently when there is a large portion of data appearing only once.
The U.S. patent to Govindarajan et al. (U.S. Pat. No. 6,006,234) describes access control using logical groups in database, where the described grouping is not the grouping in a query, but deal with logical grouping of database objects.
Whatever the precise merits, features, and advantages of the above cited references, none of them achieves or fulfills the purposes of the present invention.